Aravindan Vijayaraghavan
Graph Partitioning problems like Balanced Cut form a central topic of study in computer science. However, good guarantees (e.g. constant factor approximations) have been elusive for many of these problems. Since real-world instances are unlikely to behave like worst-case instances, a compelling question is : can we design better algorithms for real-world instances?
In this talk, I will discuss two paradigms that go beyond traditional worst-case analysis: (realistic) average-case analysis, and instance stability. I will use these paradigms to show significantly better guarantees for graph partitioning.
In the first part of the talk, I will introduce new average-case models for graph partitioning that are more general that previous models, and that we believe, capture many properties of real-world instances. I will then present a new algorithmic framework based on semidefinite programming that gives constant factor approximation algorithms in these average-case models. In the second part of the talk, I will describe how convex relaxations for certain graph partitioning problems become integral on instances that satisfy a natural notion of stability introduced by Bilu and Linial.
Based on joint works with Konstantin Makarychev and Yury Makarychev.